package com.algorithm.ch1.hf.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定两个数组，写一个方法来计算它们的交集。

 例如:
 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

 注意：

 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
 我们可以不考虑输出结果的顺序。
 跟进:

 如果给定的数组已经排好序呢？你将如何优化你的算法？
 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
 */
public class Intersect {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 2, 1};
        int[] nums2 = new int[]{2};
        int[] repeat = same(nums1, nums2);

        System.out.print("repeat elements :[");
        for (int i : repeat) {
            System.out.print(i+",");
        }
        System.out.print("]");
    }

    //交集
    public static int[] same(int[] nums1 ,int[] nums2 ){
        int[] ints = new int[nums1.length < nums2.length ? nums1.length : nums2.length];
        int index = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int Indexb = 0;
        for(int a = 0;a < nums1.length;a++) {
            for(int b = Indexb; b <nums2.length; b++) {
                if(nums1[a] == nums2[b]) {
                    Indexb = b + 1;
                    ints[index] = nums1[a];
                    index++;
                    break;
                }
            }

        }
        return Arrays.copyOf(ints,index);
    }

    //次数需一致
    public static int[] repeat(int[] nums1 ,int[] nums2 ){
        int[] ints = new int[nums1.length>nums2.length?nums1.length:nums2.length];
        int temp = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        //相同数字的数量。。
        int start = 0;
        int end = 0;
        for(int i = 0;i < nums1.length;i++) {
            if(i >= nums1.length - 1 || nums1[i + 1] != nums1[i]) {
                end = i;
                for(int a = 0;a < nums2.length;a++) {
                    if(nums2[a] == nums1[i]) {
                        boolean flag = true;
                        for(int x = a;x<a+end -start + 1;x++) {
                            if(x >= nums2.length || nums2[x] != nums2[a]) {
                                flag = false;
                            }
                        }
                        if(flag) {
                           for(int index = 0; index < end - start + 1;index++) {
                               ints[temp] = nums1[i];
                               temp++;
                           }
                        }
                        //跳出第二个数组的循环
                        break;
                    }
                }
                start = i + 1;
            }
        }
        return Arrays.copyOf(ints,temp);
    }

}
